package easy;

/**
 * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，
 * 则返回 true ，否则返回 false 。
 * 
 * 进阶：不要 使用任何内置的库函数，如 sqrt 。
 *
 * 示例 1：
 * 输入：num = 16
 * 输出：true
 *
 * 示例 2：
 * 输入：num = 14
 * 输出：false
 *
 *  提示：
 *  1 <= num <= 2^31 - 1 
 *  
 *  Related Topics 数学 二分查找 
 *  👍 327 👎 0
 */

public class L367_有效的完全平方数 {
    public static void main(String[] args) {
        System.out.println(new L367_有效的完全平方数().isPerfectSquare(2147483647));
    }

    /**
     * 使用Java API.
     *
     * 解答成功:
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:35.3 MB,击败了30.05% 的Java用户
     */
    public boolean isPerfectSquare(int num) {
        int tmp = (int)Math.sqrt(num);
        return tmp * tmp == num;
    }

    /**
     * 二分法.
     *
     * 解答成功:
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:35.1 MB,击败了85.85% 的Java用户
     */
    public boolean isPerfectSquare2(int num) {
        int left = 0;
        int right = num;

        while(left <= right){
            int med = (left + right)/2;
            long tmp = (long) med * med;
            if (tmp < num){
                left = med + 1;
            } else if (tmp > num){
                right = med - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
